#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "galois.h"

int galois_split_multiply(int x, int y, int **galois_split_tables, int sections, int sos) {
  int a, b, accumulator, i8, j8;
  int i, j;
  int index_mod;

  accumulator = 0;
  index_mod = 0;
  for (i = 0; i < sos; i++) {
   index_mod |= (1 << i);
  }

  i8 = 0;
  for (i = 0; i < sections; i++) {
    a = (((x >> i8) & index_mod) << sos);
    j8 = 0;
    for (j = 0; j < sections; j++) {
      b = ((y >> j8) & index_mod);
      accumulator ^= galois_split_tables[i+j][a|b];
      j8 += sos;
    }
    i8 += sos;
  }
  return accumulator;
}

main (int argc, char **argv)
{
  int **galois_split_tables;
  int p1, p2, i, j, p1elt, p2elt, index, ishift, jshift, *table;
  int sos, total_tables, w, sections;
  int a, b;

  if (argc != 3) {
    fprintf(stderr, "usage: prog w size_of_split\n");
    exit(1);
  }

  w = atoi(argv[1]);
  if (w <= 0 || w > 32 || w%2 != 0) {
     fprintf(stderr, "Bad value for w: %d\n", w);
     exit(1);
  }

  sos = atoi(argv[2]);
  if (sos >= w || sos <= 0 || w % sos != 0) {
    fprintf(stderr, "Bad value for SoS: %d\n", sos);
    exit(1);
  }
  
  sections = w/sos;
  
  total_tables = sections*2 - 1;
  galois_split_tables = (int **) malloc (sizeof(int *) * total_tables);

  for (i = 0; i < total_tables; i++) {
    galois_split_tables[i] = (int *) malloc(sizeof(int) * (1 << sos) * (1 << sos));
    if (galois_split_tables[i] == NULL) {
      for (i--; i >= 0; i--) free(galois_split_tables[i]);
      return -1;
    }
  }

  for (i = 0; i < sections; i+=(sections-1)) {
    ishift = i * sos;
    for (j = (i == 0)? 0 : 1; j < sections; j++) {
      jshift = j * sos;
      table = galois_split_tables[i+j];
      index = 0;
      for (p1 = 0; p1 < (1 << sos); p1++) {
        p1elt = (p1 << ishift);
        for (p2 = 0; p2 < (1 << sos); p2++) {
          p2elt = (p2 << jshift);
          table[index] = galois_shift_multiply(p1elt, p2elt, w);
          index++;
        }
      } 
    }
  }
  
  j = 0;
  for (i = 0; i < w; i++) {
    j |= (1 << i);
  }
  srand48(time(0));
  for (i = 0; i < 1000; i++) {
    for (a = lrand48() & j; a == 0; a = lrand48() & j);
    for (b = lrand48() & j; b == 0; b = lrand48() & j);
    printf("a: %6d b: %6d\n", a, b);
    fflush(stdout);
    printf("shift_mult:    %d\n", galois_shift_multiply(a, b, w));
    printf("split_tables:  %d\n\n", galois_split_multiply(a, b, galois_split_tables, sections, sos));
  }
}
